#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<unordered_set>

using namespace std;

int maximumSum(vector<int>& arr) {
    int f0 = arr[0], f1 = 0, res = arr[0];
    for (int i = 1; i < arr.size(); i++)
    {
        f1 = max(f0, f1 + arr[i]);
        f0 = max(f0, 0) + arr[i];
        res = max(res, max(f0, f1));
    }
    return res;
}

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> us;
    for (auto it : wordDict) us.insert(it);

    vector<bool> f(s.size());
    f[0] = true;
    for (int i = 1; i <= s.size(); i++)
    {
        for (int j = 0; j < i; j++)
            if (f[j] && us.find(s.substr(j, i - j)) != us.end())
            {
                f[i] = true;
                break;
            }
    }
    return f[s.size()];
}